import math
n=7168

def numSquares(n):
    dp=[i*i for i in range(1,math.floor(math.sqrt(n))+1)]
    #广度优先遍历求解
    queue_list=[n]
    state_set=set(queue_list)
    is_find=False
    level=0
    while not is_find:
        queue_len=len(queue_list)
        print("_____________________________________")
        print(queue_list)
        print(dp)
        print("______________________________________")
        level+=1
        while queue_len>0 and not is_find:
            top_elem=queue_list.pop(0)
            print("top_elem:",top_elem)
            si=False
            for i in dp:
                sub_elem=top_elem-i
                if sub_elem==0:
                    is_find=True
                    break
                elif sub_elem>0:
                    if sub_elem not in state_set:
                        state_set.add(sub_elem)
                        queue_list.append(sub_elem)
            #     else:
            #         si=True
            # if si:
            #     dp.pop(len(dp)-1)
            queue_len-=1
        if queue_list[0]<dp[len(dp)-1]:
            dp.pop(len(dp)-1)
    print("最终结果:",level)
def numSquares1(n):
    dp=[0 for _ in range(n+1)]
    for i in range(1,1+n):
        #最坏的情况就是每次+1
        dp[i]=i
        j=1
        while i-j*j>=0:
            dp[i]=min(dp[i],dp[i-j*j]+1)  #动态转移方程
            j+=1
    return dp[n]
print(numSquares1(n))